package com.my.algorithmlearning.leetcode;

import org.springframework.util.Assert;

import java.util.Arrays;

/**
 * @ClassName MajorityElement
 * @Description MajorityElement
 * @Author wanghaiwei
 * @Date 2023/1/6 10:01
 */
public class MajorityElement {
    public int majorityElementBySort(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length >> 1];
    }

    public int majorityElementByMoore(int[] nums) {
        int candidate = nums[0];
        int votes = 1;
        for (int i = 1; i < nums.length; i++) {
            if(votes == 0) {
                candidate = nums[i];
                votes = 1;
            }else if (nums[i] == candidate) {
                votes++;
            }else {
                votes--;
            }
        }
        return candidate;
    }

    public static void main(String[] args) {
        MajorityElement solution = new MajorityElement();
        Assert.isTrue(solution.majorityElementBySort(new int[]{3,2,3}) == 3, "majorityElementBySort nums = [3,2,3]计算失败");
        Assert.isTrue(solution.majorityElementBySort(new int[]{2,2,1,1,1,2,2}) == 2, "majorityElementBySort nums = [2,2,1,1,1,2,2]计算失败");
        Assert.isTrue(solution.majorityElementByMoore(new int[]{3,2,3}) == 3, "majorityElementByMoore nums = [3,2,3]计算失败");
        Assert.isTrue(solution.majorityElementByMoore(new int[]{2,2,1,1,1,2,2}) == 2, "majorityElementByMoore nums = [2,2,1,1,1,2,2]计算失败");
    }
}
